package BitManipulation;

import java.util.ArrayList;
import java.util.List;

public class _260_SingleNumberIII {
    //solution 1:use twice loop and compare,slow
    public int[] singleNumber_0(int[] nums) {
        List<Integer> results = new ArrayList<>();
        boolean[] twices = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    twices[i] = true;
                    twices[j] = true;
                    break;
                }
            }
        }
        for (int i = 0; i < twices.length; i++) {
            if (!twices[i]) {
                results.add(nums[i]);
            }
        }
        int[] numbers = new int[results.size()];
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = results.get(i);
        }
        return numbers;
    }

    //reference solution 2:use a bit that the two single number different from each other to
    //seperate them
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int n : nums) {
            xor ^= n;
        }
        int diff = xor & (-xor);//get the last different bit's 1
        int[] results = {0, 0};
        for (int n : nums) {
            if ((diff & n) == 0) {
                results[0] ^= n;
            } else {
                results[1] ^= n;
            }
        }
        return results;
    }
}
